package com.lzq.leetcode.hoot100;

import java.util.TreeMap;

public class s215 {
    // 3, 4, 5, 1, 2
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, 0, nums.length-1, nums.length-k);
    }

    private int quickSort(int[] nums, int l, int r, int k) {
        if (l == r) return nums[l];
        // 选择第一个
        int star = l, end = r;
        int t = nums[star];
        --l;
        ++r;
        while (l < r) {
            do  l++;    while(nums[l] < t);
            do  r--;    while(nums[r] > t);
            if (l < r) {
                swap(nums, l, r);
            }
        }
        if (r <= k)  return quickSort(nums, r+1, end, k);
        else    return quickSort(nums, star, r, k);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        s215 s215 = new s215();
        System.out.println(s215.findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4));

        String str = "{\n\"ip\" : \"192.168.9.211\",\n\"agentId\": \"1000002\",\n\"direction\": \"inbound\"\n}";
    }


}
